import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

public class MinmumNumberOfHost {
    // 通过93%
    public int minmumNumberOfHost (int n, int[][] startEnd) {
        // write code here
        if (n == 1) {
            return 1;
        }
        Arrays.sort(startEnd, (a, b) -> {
            return a[0] == b[0] ? a[1]-b[1] : a[0]-b[0];
        });
        int max = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        queue.offer(startEnd[0][1]);
        for (int i = 1; i < startEnd.length; i++) {
            while (queue.size() > 0 && queue.peek() <= startEnd[i][0]) {
                queue.poll();
            }
            if (queue.size() == 0 || startEnd[i][0] < queue.peek()) {
                queue.offer(startEnd[i][1]);
            }
            max = Math.max(max, queue.size());
        }
        return max;
    }

    // 通过100%
    public int minmumNumberOfHost1(int n, int[][] startEnd) {
        List<int[]> events = new ArrayList<>();

        for (int[] interval : startEnd) {
            events.add(new int[]{interval[0], 1});  // 主持人上场
            events.add(new int[]{interval[1], -1}); // 主持人下场
        }

        // 避免溢出，确保排序稳定
        events.sort((a, b) ->
                a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1])
        );

        int max = 0, count = 0;
        for (int[] event : events) {
            count += event[1];
            max = Math.max(max, count);
        }

        return max;
    }
}
